package java_core.day;

import java.util.*;

public class Day5_24 {

    public static void main(String[] args) {
        System.out.println(checkPossibility(new int[]{2,3,3,2,4}));
    }


    /*914. 卡牌分组 https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/
    给定一副牌，每张牌上都写着一个整数。
    此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
    每组都有 X 张牌。
    组内所有的牌上都写着相同的整数。
    仅当你可选的 X >= 2 时返回 true。
    示例 1：
    输入：[1,2,3,4,4,3,2,1]
    输出：true
    解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]*/

    //分析,就是看数字出现的次数是否一样并且是否大于2,利用数组
    private static boolean hasGroupsSizeX(int[] deck) {
        int[] index = new int[10000];
        for (int i = 0; i < deck.length; i++) {
            index[deck[i]]++;
        }
        int newMinCount = 0;
        int oldMinCount = 0;
        int compareNumber = 0;
        //获取出现次数的最大公因子
        for (int i = 0; i < index.length; i++) {
            if (index[i] == 1) {
                return false;
            }
            if (index[i] > 1) {
                if (oldMinCount == 0) {

                    oldMinCount = index[i];
                    newMinCount = oldMinCount;
                } else {
                    compareNumber = index[i];
                    oldMinCount = newMinCount;
                    newMinCount = gcd(oldMinCount, compareNumber);
                    //最大公因子等于1说明不能分组
                    if (newMinCount < 2) {
                        return false;
                    }
                    newMinCount = Math.min(newMinCount, oldMinCount);
                }

            }
        }

        //判断数字出现的次数是否是最大公因子的整数倍
        for (int i = 0; i < index.length; i++) {
            if (index[i] % newMinCount != 0) {
                return false;
            }
        }
        return true;

    }

    /**
     * gcd算法,求出a和b的最大公因子
     */
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    //===============================================================================================
    /*153. 寻找旋转排序数组中的最小值 https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。
    ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
    请找出其中最小的元素。
    你可以假设数组中不存在重复元素。
    示例 1:
    输入: [3,4,5,1,2]
    输出: 1
    示例 2:
    输入: [4,5,6,7,0,1,2]
    输出: 0*/
    //可以使用二分法
    private int findMin(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }


    //===============================================================================================
    /*1160. 拼写单词 https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/
    给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
    假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
    注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
    返回词汇表 words 中你掌握的所有单词的 长度之和。
    示例 1：
    输入：words = ["cat","bt","hat","tree"], chars = "atach"
    输出：6
    解释：
    可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。*/
    private int countCharacters_1160(String[] words, String chars) {
        int count = 0;
        for (String word : words) {
            if (compareTwoString(chars, word)) {
                count += word.length();
            }
        }
        return count;
    }

    private boolean compareTwoString(String str1, String str2) {
        int[] arr = new int[128];
        for (int i = 0; i < str1.length(); i++) {
            arr[str1.charAt(i)]++;
            if (i < str2.length()) {
                arr[str2.charAt(i)]--;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                return false;
            }
        }
        return true;
    }

    //===============================================================================================
/*    336. 回文对 https://leetcode-cn.com/problems/palindrome-pairs/
    给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
    示例 1:
    输入: ["abcd","dcba","lls","s","sssll"]
    输出: [[0,1],[1,0],[3,2],[2,4]]
    解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
    示例 2:
    输入: ["bat","tab","cat"]
    输出: [[0,1],[1,0]]
    解释: 可拼接成的回文串为 ["battab","tabbat"]*/

    //满足要求,但是超时
    public List<List<Integer>> palindromePairs1_336(String[] words) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            StringBuilder stringBuilder = new StringBuilder(words[i]);
            for (int j = i + 1; j < words.length; j++) {
                stringBuilder.append(words[j]);
                if (isHuiWenStr(stringBuilder.substring(stringBuilder.length() - words[i].length() - words[j].length()))) {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    lists.add(list);
                }
                stringBuilder.append(words[i]);
                if (isHuiWenStr(stringBuilder.substring(stringBuilder.length() - words[i].length() - words[j].length()))) {
                    List<Integer> list = new ArrayList<>();
                    list.add(j);
                    list.add(i);
                    lists.add(list);
                }
            }
        }

        return lists;
    }

    //判断是否是回文字符串
    private boolean isHuiWenStr(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    //前缀树方法 ok
    public List<List<Integer>> palindromePairs2_336(String[] words) {
        Map<String, Integer> hm = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        // 将所有的字符串反转
        for (int i = 0; i < words.length; i++) {
            hm.put(new StringBuilder(words[i]).reverse().toString(), i);
        }

        // 找所有可能的后缀
        for (int i = 0; i < words.length; i++) {
            String tmp = words[i];
            for (int j = 0; j < tmp.length(); j++) {
                if (isParmlind(tmp, j, tmp.length() - 1)) {
                    String suffix = tmp.substring(0, j);
                    if (hm.containsKey(suffix)) {
                        if (hm.get(suffix) != i) {
                            res.add(new ArrayList<Integer>(Arrays.asList(i, hm.get(suffix))));
                        }
                    }
                }
            }

            // 找所有可能的前缀
            for (int j = tmp.length() - 1; j >= 0; j--) {
                if (isParmlind(tmp, 0, j)) {
                    String prefix = tmp.substring(j + 1);
                    if (hm.containsKey(prefix)) {
                        if (hm.get(prefix) != i) {
                            res.add(new ArrayList<Integer>(Arrays.asList(hm.get(prefix), i)));
                        }
                    }
                }
            }
            if (hm.containsKey(tmp)) {
                if (i != hm.get(tmp)) {
                    res.add(new ArrayList<Integer>(Arrays.asList(i, hm.get(tmp))));
                }
            }
        }
        return res;
    }

    private boolean isParmlind(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }


    //===============================================================================================
    /*713. 乘积小于K的子数组 https://leetcode-cn.com/problems/subarray-product-less-than-k/
    给定一个正整数数组 nums。
    找出该数组内乘积小于 k 的连续的子数组的个数。
    示例 1:
    输入: nums = [10,5,2,6], k = 100
    输出: 8
    解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
    需要注意的是 [10,5,2] 并不是乘积小于100的子数组。*/

    //超时
    public static int numSubarrayProductLessThanK1_713(int[] nums, int k) {
        int count = 0;
        int preNum;
        for (int i = 0; i < nums.length; i++) {
            preNum = nums[i];
            if (nums[i] < k) {
                count++;
            } else {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if ((preNum = preNum * nums[j]) < k) {
                    count++;
                } else {
                    break;
                }
            }
        }
        return count;
    }

    //滑动窗口+双指针 ok
    public int numSubarrayProductLessThanK2_713(int[] nums, int k) {
        if (k <= 1) return 0;

        // 存储乘积小于K的子数组的个数
        int ans = 0;
        // 当前窗口的所有元素的乘积
        int prod = 1;

        // 维护滑动窗口
        int left = 0;
        int right = 0;
        while (right < nums.length) {
            // 更新当前窗口的累计乘积
            prod *= nums[right];
            // left 指针移动
            // 移动时机：当前窗口累计乘积大于等于 k
            // 移动策略：将累计乘积除以需要移除的左边的元素值
            while (prod >= k) {
                prod /= nums[left++];
            }

            // 到现在当前窗口的乘积小于 k
            // 计算乘积小于 k 的子数组的个数
            ans += right - left + 1;

            // right 指针移动
            right++;
        }

        return ans;
    }


    //===============================================================================================
    /*560. 和为K的子数组 https://leetcode-cn.com/problems/subarray-sum-equals-k/
    给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
    示例 1 :
    输入:nums = [1,1,1], k = 2
    输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。*/
    //ok 也可使用滑动窗口
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int preNum;
        for (int i = 0; i < nums.length; i++) {
            preNum = nums[i];
            if (nums[i] == k) {
                count++;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if ((preNum = preNum + nums[j]) == k) {
                    count++;
                }
            }
        }
        return count;
    }

    //===============================================================================================
    /*862. 和至少为 K 的最短子数组 https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/
    返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
    如果没有和至少为 K 的非空子数组，返回 -1 。
    示例 1：
    输入：A = [1], K = 1
    输出：1
    示例 2：
    输入：A = [1,2], K = 4
    输出：-1
    示例 3：
    输入：A = [2,-1,2], K = 3
    输出：3*/

    //暴力法, 超时 me
    public static int shortestSubarray1_862(int[] A, int K) {
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= 0) {
                continue;
            }
            sum = A[i];
            right = i + 1;
            //
            while (sum < K && right < A.length) {
                sum += A[right++];
            }
            if (sum >= K)
                minLength = Math.min(minLength, right - i);

        }
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }

    // ok https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/solution/he-zhi-shao-wei-k-de-zui-duan-zi-shu-zu-by-leetcod/
    public int shortestSubarray2_862(int[] A, int K) {
        int N = A.length;
        long[] P = new long[N+1];
        for (int i = 0; i < N; ++i)
            P[i+1] = P[i] + (long) A[i];

        // Want smallest y-x with P[y] - P[x] >= K
        int ans = N+1; // N+1 is impossible
        Deque<Integer> monoq = new LinkedList(); //opt(y) candidates, as indices of P

        for (int y = 0; y < P.length; ++y) {
            // Want opt(y) = largest x with P[x] <= P[y] - K;
            while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
                monoq.removeLast();
            while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
                ans = Math.min(ans, y - monoq.removeFirst());

            monoq.addLast(y);
        }

        return ans < N+1 ? ans : -1;
    }


    //===============================================================================================
    /*5. 最长回文子串 https://leetcode-cn.com/problems/longest-palindromic-substring/
    给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    示例 1：
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    示例 2：
    输入: "cbbd"
    输出: "bb"*/
    public String longestPalindrome1_5(String s) {

        return null;
    }


    //===============================================================================================
    //665. 非递减数列
    public static boolean checkPossibility(int[] nums) {
        //3,4,2,3
        for (int i = nums.length-1; i >0 ; i--) {
            if (nums[i] < nums[i - 1]) {
                nums[i] = nums[i-1];
                break;
            }
        }
        for (int i = nums.length-1; i >0 ; i--) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return true;
    }

}
